//给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。 
//
// 环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个
//元素是 nums[(i - 1 + n) % n] 。 
//
// 子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], ..., nums[j] ，不
//存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,-2,3,-2]
//输出：3
//解释：从子数组 [3] 得到最大和 3
// 
//
// 示例 2： 
//
// 
//输入：nums = [5,-3,5]
//输出：10
//解释：从子数组 [5,5] 得到最大和 5 + 5 = 10
// 
//
// 示例 3： 
//
// 
//输入：nums = [3,-2,2,-3]
//输出：3
//解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3
// 
//
// 
//
// 提示： 
//
// 
// n == nums.length 
// 1 <= n <= 3 * 10⁴ 
// -3 * 10⁴ <= nums[i] <= 3 * 10⁴ 
// 
//
// Related Topics 队列 数组 分治 动态规划 单调队列 👍 751 👎 0


package LeetCode.editor.cn;


import java.util.*;

/**
 * @author ldltd
 * @date 2024-11-04 16:06:45
 * @description 918.环形子数组的最大和
 
 */
 
public class MaximumSumCircularSubarray {
    public static void main(String[] args) {
    //测试代码
    MaximumSumCircularSubarray fun = new MaximumSumCircularSubarray();
    Solution solution= fun.new Solution();
    int []ar=new int[]{3,-2,2,-3};
    int []br=new int[]{5,-3,5};
    int []cr=new int[]{-3,-2,-3};
        System.out.println(solution.maxSubarraySumCircular(cr));
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        /*
        *1.如果没有跨区间，则相当于求最大非空子数组和
        *2.如果跨区间了，则，首尾中间省的数越小，跨区见余下的数越大
        *3.最小子数组有可能就是整个数组，需要排除
        * */
    public int maxSubarraySumCircular(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        int max=helper(nums,true);
        int min=helper(nums,false);
        if(min==sum) return max;
        return Math.max(max,sum-min);
    }
    //true 返回最大子数组，false最小子数组
    public int helper(int [] nums,boolean f){
        int res=f?-30001:30001;
        int t=0;
        for (int num : nums) {
            t+=num;
            res=f? Math.max(res,t):Math.min(res,t);
            if(f&&t<0) t=0;
            if(!f&&t>0)t=0;
        }
        return res;
    }
    //一次遍历，minF,maxF是中间量
    public int maxSubarraySumCircular1(int[] nums) {
         int maxS = Integer.MIN_VALUE; // 最大子数组和，不能为空
         int minS = 0;//最小子数组和，可以为空
         int maxF = 0, minF = 0, sum = 0;
         for (int x : nums) {
             // 以 nums[i-1] 结尾的子数组选或不选（取 max）+ x = 以 x 结尾的最大子数组和
             maxF = Math.max(maxF, 0) + x;
             maxS = Math.max(maxS, maxF);
             // 以 nums[i-1] 结尾的子数组选或不选（取 min）+ x = 以 x 结尾的最小子数组和
             minF = Math.min(minF, 0) + x;
             minS = Math.min(minS, minF); sum += x;
         }
         return sum == minS ? maxS : Math.max(maxS, sum - minS);
    }
    //单调队列，维护前缀和和单调队列q，计算si-sj，其中i-n<=j<i
    public int maxSubarraySumCircular2(int[] nums) {
        int n = nums.length;
        Deque<int[]> queue = new ArrayDeque<int[]>();
        int pre = nums[0], res = nums[0];
        queue.offerLast(new int[]{0, pre});
        for (int i = 1; i < 2 * n; i++) {
            //如果头部下标小于i-n，一直出队
            while (!queue.isEmpty() && queue.peekFirst()[0] < i - n) {
                queue.pollFirst();
            }
            //取头部j计算si-sj更新答案
            pre += nums[i % n];
            //如果队尾元素k sk>=si则一直出队
            //即前面的前缀和大于后面的，说明在减少，要么是 + - +，要么是+ -
            //+ — +相当于，跳过中间-的，+ -相当于跳过负数，因为每一轮都会计算结果，所以可以跳过
            res = Math.max(res, pre - queue.peekFirst()[1]);
            while (!queue.isEmpty() && queue.peekLast()[1] >= pre) {
                queue.pollLast();
            }
            //保存的是下标和当前下标的前缀和
            queue.offerLast(new int[]{i, pre});
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
